{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. 两数之和  \n",
    "给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。  \n",
    "你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。  \n",
    "示例:  \n",
    "给定 nums = [2, 7, 11, 15], target = 9  \n",
    "因为 nums[0] + nums[1] = 2 + 7 = 9  \n",
    "所以返回 [0, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def twoSum(nums, target):\n",
    "    nums_length = len(nums)\n",
    "#     暴力法\n",
    "#     for i in range(nums_length):\n",
    "#         for j in range(i + 1, nums_length):\n",
    "#             if nums[i] + nums[j] == target:\n",
    "#                 return [i, j]\n",
    "\n",
    "#     一遍哈希表\n",
    "#     d = dict()\n",
    "#     for i in range(nums_length):\n",
    "#         tmp = target - nums[i]\n",
    "#         if tmp in d:\n",
    "#             return [d[tmp], i]\n",
    "#         d[nums[i]] = i\n",
    "\n",
    "#   一行代码\n",
    "    return [[i, nums.index(target - nums[i])] for i in range(nums_length) if (target - nums[i]) in nums and i != nums.index(target - nums[i])][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3]\n"
     ]
    }
   ],
   "source": [
    "print(twoSum([2, 7, 11, 15], 22))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7. 整数反转\n",
    "给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。  \n",
    "示例 1:  \n",
    "输入: 123  \n",
    "输出: 321  \n",
    " 示例 2:  \n",
    "输入: -123  \n",
    "输出: -321  \n",
    "示例 3:  \n",
    "输入: 120  \n",
    "输出: 21  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def reverse(x):\n",
    "        # 字面理解转成字符串直接干，简单粗暴\n",
    "        # s = str(x) if x >= 0 else str(x)[1:]\n",
    "        # rev_s = s[::-1]\n",
    "        # ans = int(rev_s) if x >= 0 else 0 - int(rev_s)\n",
    "        # if ans < -2 ** 31 or ans > 2 ** 31 - 1:\n",
    "        #     return 0\n",
    "        # return ans\n",
    "        # 正儿八经，弹出个位数，好在python int类型范围大\n",
    "        y , rev = abs(x), 0\n",
    "        while y != 0:\n",
    "            pop = y % 10\n",
    "            y = y // 10\n",
    "            rev = rev * 10 + pop\n",
    "        rev = rev if x >=0 else -rev\n",
    "        if rev < -2 ** 31 or rev > 2 ** 31 - 1:\n",
    "            return 0\n",
    "        return rev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "-321\n"
    }
   ],
   "source": [
    "print(Solution.reverse(-123))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9. 回文数\n",
    "判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。  \n",
    "示例 1:  \n",
    "输入: 121  \n",
    "输出: true  \n",
    "示例 2:  \n",
    "输入: -121  \n",
    "输出: false  \n",
    "解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。  \n",
    "示例 3:  \n",
    "输入: 10  \n",
    "输出: false  \n",
    "解释: 从右向左读, 为 01 。因此它不是一个回文数。  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def isPalindrome(x):\n",
    "        # 试下不用字符串\n",
    "        if x < 0: return False\n",
    "        res = 0\n",
    "        y = x\n",
    "        while y >= 10:\n",
    "            i = y % 10\n",
    "            res = res * 10 + i\n",
    "            y = y // 10\n",
    "        res = res * 10 + y\n",
    "        return True if x == res else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "False\n"
    }
   ],
   "source": [
    "print(Solution.isPalindrome(123))"
   ]
  },
  {
   "source": [
    "### 13.罗马数字转整数\n",
    "罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。  \n",
    "字符          数值  \n",
    "I             1  \n",
    "V             5  \n",
    "X             10  \n",
    "L             50  \n",
    "C             100  \n",
    "D             500  \n",
    "M             1000  \n",
    "例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。  \n",
    "通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：  \n",
    "I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。  \n",
    "X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。   \n",
    "C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。  \n",
    "给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。  \n",
    "示例 1:  \n",
    "输入: \"III\"  \n",
    "输出: 3  \n",
    "示例 2:  \n",
    "输入: \"IV\"  \n",
    "输出: 4  \n",
    "示例 3:  \n",
    "输入: \"IX\"  \n",
    "输出: 9  \n",
    "示例 4:  \n",
    "输入: \"LVIII\"  \n",
    "输出: 58  \n",
    "解释: L = 50, V= 5, III = 3.  \n",
    "示例 5:  \n",
    "输入: \"MCMXCIV\"  \n",
    "输出: 1994  \n",
    "解释: M = 1000, CM = 900, XC = 90, IV = 4.  "
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def romanToInt(s):\n",
    "        ref = {\n",
    "            'I': 1,\n",
    "            'V': 5,\n",
    "            'X': 10,\n",
    "            'L': 50,\n",
    "            'C': 100,\n",
    "            'D': 500,\n",
    "            'M': 1000\n",
    "        }\n",
    "        res = 0\n",
    "        for i in range(len(s) - 1):\n",
    "            if ref[s[i]] < ref[s[i + 1]]:\n",
    "                res -= ref[s[i]]\n",
    "            else:\n",
    "                res += ref[s[i]]\n",
    "        res += ref[s[-1]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "1994\n"
    }
   ],
   "source": [
    "print(Solution.romanToInt('MCMXCIV'))"
   ]
  },
  {
   "source": [
    "### 14.最长公共前缀\n",
    "编写一个函数来查找字符串数组中的最长公共前缀。 \n",
    "如果不存在公共前缀，返回空字符串 \"\"。  \n",
    "示例 1:  \n",
    "输入: [\"flower\",\"flow\",\"flight\"]  \n",
    "输出: \"fl\"  \n",
    "示例 2:  \n",
    "输入: [\"dog\",\"racecar\",\"car\"]  \n",
    "输出: \"\"  \n",
    "解释: 输入不存在公共前缀。  \n",
    "说明:  \n",
    "所有输入只包含小写字母 a-z 。  "
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs) -> str:\n",
    "        # 纵向扫描比较符合直观，像array\n",
    "        if not strs: return \"\"\n",
    "        length, count = len(strs[0]), len(strs)\n",
    "        for i in range(length):\n",
    "            c = strs[0][i]\n",
    "            if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):\n",
    "                return strs[0][:i]\n",
    "        return strs[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "fl\n"
    }
   ],
   "source": [
    "a = Solution()\n",
    "print(a.longestCommonPrefix([\"flower\",\"flow\",\"flight\"]))"
   ]
  },
  {
   "source": [
    "### 15.三数之和\n",
    "给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。  \n",
    "注意：答案中不可以包含重复的三元组。  \n",
    "示例：  \n",
    "给定数组 nums = [-1, 0, 1, 2, -1, -4]，  \n",
    "满足要求的三元组集合为：  \n",
    "[  \n",
    "  [-1, 0, 1],  \n",
    "  [-1, -1, 2]  \n",
    "]  "
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def threeSum(self, nums):\n",
    "        # 会超时。。。\n",
    "        # length = len(nums)\n",
    "        # nums = sorted(nums)\n",
    "        # result = list()\n",
    "        # for i in range(length - 2):\n",
    "        #     if nums[i] > 0: break\n",
    "        #     if i > 0 and nums[i] == nums[i - 1]: continue\n",
    "        #     for j in range(i + 1, length - 1):\n",
    "        #         if nums[j] == nums[j - 1] and j > i + 1: continue\n",
    "        #         for k in range(length - 1, j, -1):\n",
    "        #             if nums[k] < 0: break\n",
    "        #             if nums[k] == nums[k - 1] and k > j + 1: continue\n",
    "        #             if nums[i] + nums[j] + nums[k] == 0:\n",
    "        #                 result.append([nums[i], nums[j], nums[k]])\n",
    "        # return result\n",
    "        \n",
    "        # 利用双指针\n",
    "        length = len(nums)\n",
    "        nums = sorted(nums)\n",
    "        res = list()\n",
    "        for i in range(length):\n",
    "            if i > 0 and nums[i] == nums[i - 1]: continue\n",
    "            if nums[i] > 0: break\n",
    "            L, R = i + 1, length - 1\n",
    "            while L < R:\n",
    "                if L + 1 < R and nums[L] == nums[L + 1]:\n",
    "                    L += 1\n",
    "                    continue\n",
    "                elif R - 1 > L and nums[R] == nums[R - 1]:\n",
    "                    R -= 1\n",
    "                    continue\n",
    "                if nums[i] + nums[L] + nums[R] == 0:\n",
    "                    res.append([nums[i], nums[L], nums[R]])\n",
    "                    L += 1\n",
    "                    R -= 1\n",
    "                elif nums[i] + nums[L] + nums[R] > 0:\n",
    "                    R -= 1\n",
    "                else:\n",
    "                    L += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "[[-5, -4, 9], [-5, -3, 8], [-5, -2, 7], [-5, -1, 6], [-5, 0, 5], [-4, -3, 7], [-4, -2, 6], [-4, -1, 5], [-4, 0, 4], [-3, -2, 5], [-3, -1, 4]]\n"
    }
   ],
   "source": [
    "a = Solution()\n",
    "print(a.threeSum([-5,-5,-4,-3,-2,-1,0,4,5,6,7,8,9]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.5 64-bit",
   "language": "python",
   "name": "python38564bitecc3c6c20b6d476e9f76c858db0e1781"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5-final"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}